In an unweighted graph, the `level` of a node found by BFS is its shortest distance from the source. We can reconstruct the path by backtracking.

  • The `level[v]` calculated by BFS from source `s` equals the minimum number of edges on any path from `s` to `v`.
  • This is the core reason BFS is used for finding shortest paths in unweighted graphs.
  • To find the actual path, we use the `parent` map and work backwards from the target node `t`.
  • By repeatedly looking up the parent of the current node (`parent[x]`), we trace a path back to the source `s`, which has a `null` parent.
  • The collected sequence of nodes, when reversed, gives the shortest path from `s` to `t`.
reconstruct_path.py
def reconstruct_path(parent, s, t):
    if t not in parent:
        return "unreachable"
    path = []
    x = t
    while x is not None:
        path.append(x)
        x = parent[x]
    return path[::-1]  # Reverse the path